package PolishNotation;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 中缀表达式转后缀表达式
 * Author：zouran
 * Date：2023/4/30  15:04
 */
public class MiddleToSuffix {
    //记录中缀表达式
    private final List<String> preffixList = new ArrayList<>();
    //记录运算符栈
    private final Stack<String> operateStack = new Stack<>();
    //记录后缀表达式
    private final List<String> suffixList = new ArrayList<>();

    //无参构造初始化 9+7*(12+3)%((28-12)/4)
    public MiddleToSuffix() {
        String[] strings1 = new String[]{"9", "+", "7", "*", "(", "12", "+", "3", ")", "%", "(", "(", "28", "-", "12", ")", "/", "4", ")"};
        preffixList.addAll(Arrays.asList(strings1));
    }

    //实参构造
    public MiddleToSuffix(List<String> list) {
        preffixList.addAll(list);
    }

    //判断是数字还是运算符,1为数字,2为运算符,0为未识别
    //默认识别 +，-，*，/，%，（），sqrt运算符
    public int judgeString(String s) {
        char[] chars = s.toCharArray();
        int i;
        //正数的情况
        for (i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (c < '0' || c > '9') {
                break;
            }
        }
        //负数的情况
        if (chars[0] == '-' && chars.length > 1) {
            for (i = 1; i < chars.length; i++) {
                char c = chars[i];
                if (c < '0' || c > '9') {
                    break;
                }
            }
        }
        if (i == chars.length)
            return 1;
        switch (s) {
            case "(", ")", "+", "-", "*", "/", "%", "sqrt" -> {
                return 2;
            }
            default -> {
                return 0;
            }
        }

    }

    //比较运算符优先级，a对于b而言，低于返回-1，等于返回0了，大于返回1
    public int comparePriority(String a, String b) {
        int priorityA = computedPriority(a);
        int priorityB = computedPriority(b);
        return Integer.compare(priorityA, priorityB);
    }

    //计算优先级，由高到低 sqrt；*，/，%；+，-；
    //()的逻辑进行额外设置,设置为0则是便于(后其它运算符入栈,
    // (本身不用优先级入栈，直接入栈,)则不需要入栈,俩者同级为了便于出栈运算
    public int computedPriority(String s) {
        switch (s) {
            case "sqrt" -> {
                return 3;
            }
            case "*", "/", "%" -> {
                return 2;
            }
            case "+", "-" -> {
                return 1;
            }
            case "(", ")" -> {
                return 0;
            }
            default -> {
                return -1;
            }
        }
    }

    //更新运算符栈
    public void popOperateList(String s) {
        if (s.equals(")")) {
            while (!operateStack.isEmpty()) {
                //若为(，结束
                if (comparePriority(operateStack.peek(), s) == 0)
                //否则压出栈顶运算符
                {
                    //"("不算入后缀表达式
                    operateStack.pop();
                    break;
                }
                //每次出栈一个运算符
                suffixList.add(operateStack.pop());
            }
        } else {
            while (!operateStack.isEmpty()) {
                //若栈顶运算符优先级小于当前运算符优先级，结束
                if (comparePriority(operateStack.peek(), s) == -1)
                    break;
                else {
                    //否则压出栈顶运算符
                    suffixList.add(operateStack.pop());
                }
            }
        }
    }

    //运算符栈剩余的运算符全部压出
    public void popOtherOperateList() {
        while (!operateStack.isEmpty()) {
            suffixList.add(operateStack.pop());
        }
    }

    public List<String> toSuffix() {
        for (String s : preffixList) {
            //若为运算数，直接加到后缀表达式
            if (judgeString(s) == 1)
                suffixList.add(s);
                //若为运算符
            else if (judgeString(s) == 2) {
                //若为"("，直接进栈
                if (s.equals("(")) {
                    operateStack.add(s);
                    continue;
                }
                //若为")"，直接运行出栈
                if (s.equals(")")) {
                    popOperateList(s);
                    continue;
                }
                //栈为空，直接入栈
                if (operateStack.isEmpty()) {
                    operateStack.push(s);
                    continue;
                }
                //若优先级高,压入栈
                if (comparePriority(operateStack.peek(), s) == -1)
                    operateStack.push(s);
                    //若优先级低或者等于,先出栈比该运算符高或者等于的运算符，再进栈该运算符
                else {
                    popOperateList(s);
                    operateStack.push(s);
                }
            }
        }
        //剩余的运算符出栈
        popOtherOperateList();
        return suffixList;
    }

}

